The present invention relates to a method and device for memory management in digital data transfer, and especially but not necessarily memory management in the decoding of the digital data of convolution codes.
In digital data transfer, it is primarily important to get the departing data to its destination as reliably and flawlessly as possible. One alternative for achieving this, especially in a noise limited? environment, has been to use a larger transmission power. However, regulations made for practical reasons limit the highest permissible transmission power. Another alternative has been to add a redundant information to the transmitted data, which the receiver uses to correct any errors.
In a digital mobile communications network, a received signal also contains noise and channel distortions that cause bit errors, which are then (partly) corrected using an error correction code. The transmitted bit stream can be protected against errors, e.g. as depicted in FIG. 1, with a corresponding encoder 10, which includes the modulo-2 summing units 11, 12 for forming the convolution code, the shift register 13-16 for receiving the bit to be coded, input feed for the bit to be coded 17 and the encoded bit""s output bits 18, 19. The length (constraint length) of the encoder""s shift register is K=4 and the rate is xc2xd, so each bit to be coded 17 is presented as encoded by two output bits 18, 19. When a new bit is fed into the shift register 13-16 into an element 16, the bit of the element in question moves to element 15, the bit of element 15 moves to element 14 and the bit of element 14 moves to element 13. If in our example the first bit to be transferred to the shift register 16 were 1, the output bits 18, 19 would be 11. The criteria for the above are that the shift register 13-16 is empty (DDDD=0000) in the initial situation. A bit-stream encoded according to FIG. 1 is decoded on reception for example using a Viterbi algorithm. Other decoding means can also be used.
In digital data transfer, the bit string received must contain some sort of convolution code, i.e. a code containing memory, so that the Viterbi algorithm can be utilised on reception. The Viterbi algorithm performs probability decoding using the Trellis diagram to reduce the need for computation. FIG. 2 depicts the Trellis diagram 200 formed by the K=4 convolution code, in which the possible initial states 210-217 are depicted as status column 201 and the possible end states 220-227 are depicted as status column 202. The encoder""s output bits 18, 19 are depicted as values of branches 230-245. The shift register""s 13-16 elements mentioned in FIG. 1 form a status shift, in which the shift register""s elements 13-15 are the initial status of the Trellis diagram and elements 14-16 are the end status of the Trellis diagram, which are reached from the said initial states by feeding a new bit into the encoder""s 10 shift register 13-16. Two branches 230-245 leave from each state 210-217 at the time t=T to the states 220-227 at the time t=2T. The corresponding 2-bit number for each branch 230-245, i.e. each branch state 250-265, is compared to the bit pair 18, 19 encoded with the encoder 10 in FIG. 1. If, for example, the bits in the encoder""s shift register 13-16 are 0010, which signifies a state shift from the initial state 001 to the end state 010 when the next bit to be encoded is 1, the shift register""s 13-16 bits, i.e. the state shift, are now 0101 (from initial state 010 to end state 101), in which case the encoder transmits as the output bits 18 and 19, 10. The Trellis diagram states depicted in FIG. 2 are utilised in the decoding stage of the data. Several path states formed by branch states formed from individual successive state shifts are stored in the decoder""s memory. Each bit pattern to be transmitted corresponding to the branch state is compared to received, possibly incorrect, bits. When receiving new bits, the number of state shifts grows, so the memory must be continuously updated by deleting such paths that are not needed for forming the final bit to be decoded.
In the decoding of convolution codes, a so-called Viterbi decoder depicted in FIG. 3 is used, which consists of a BMU (Branch Metric Unit) 31, ACSU (Add-Compare-Select Unit) 32 and SMU (Survivor Memory Unit) 33. On receiving a bit pair, the BMU 31 calculates the metrics, i.e. the measurement of how far the received bit pair is from each, in this case 16, branch state values 250-265 corresponding to the Trellis diagram state shifts. For instance the so-called Hamming distance, i.e. by how many bits the received bits deviate at the time in question from all possible branch metrics corresponding to state shifts, can be used as a measurement. The following example consists of two different states 211, 215 at the time t=T and correspondingly the states 222, 223 at the time t=2T. The state of the Trellis diagram at the time t=T is 001 and the received bit pair is 10, in which case the metrics of the state shift 0010 (from state 001 to state 010) is 0, because the received bit pair and the value 10 of the branch in question do not deviate from one another. Another possible state shift 0011 (from state 001 to state 011) with the same received bit pair 10 would give a metric of 2, because both bits of the received bit pair 10 are now different from the branch value 01. The branches 230-245 depicting state shifts in FIG. 2 always correspond to the possible routes of one received bit pair, of which others are more probable than others and the metric must be calculated for each said branch.
The ACSU 32 depicted in FIG. 3 consists functionally of the Add part, which calculates the cumulative path metric of all paths, i.e. the distance between all possible beginnings and ends of paths; the Compare part, which compares which branch ending in an end state is the more probable choice, i.e. closer to the received bit pair; and the Select part, which selects the more probable branch and stores it to memory. The less probable branch is disqualified and if the other branch that reaches the state in question is disqualified, the entire path leading to the state in question can also be deleted from memory as unnecessary. In the following example the less probable option is disqualified for the other branch as well. As in the previous example, here we will also look at the state shift 0010 from state 001 (211) to state 010 (222), and the state shift 1011 from state 101 (215) to state 011 (223). As seen in FIG. 2, states 001 and 101 both branch off to states 010 and 011. As was earlier stated, the received bit pair was 10. The branch value in question has two probable state shifts, i.e. state shift 0010 (from state 001 to state 010 and state shift 1011 (from state 101 to state 011). State 010 (t=2T) is reached from both state 001 (t=T) with the value 10 and from state 101 (t=T) with the value 01. If the selection made by the ACSU 32 targets path branch 232, which runs through states 010 (t=2T) and 001 (t=T), branches 233, 241 lead to state 011 (t=2T) and branches 240, 241 leaving from state 101 (t=T) are disqualified. All paths running through states 010 (t=2T), 101 (t=T) (branch 240), 011 (t=2T) and 101 (t=T) (branch 241) can now be deleted from the history data. State 101 (t=T) and all paths leading thereto can now be deleted from memory as unnecessary.
In FIG. 3, the SMU 33 stores the ACSU""s selection data and defines the Trellis diagram final survivor path, which contains the possibly unencoded original bit sequence. An ACSU complying with the prior art is the so-called trace back memory 40 depicted in FIG. 4, the memory space of which consists of consecutive Trellis diagram states in the form of address books and functionally consists of the following parts. A write block 41, in which the decisions coming from the ACSU 32 are received for expressing the Trellis diagram state shifts, and a read region 42, 43, which is further divided into a merge block 42 and a decode block 43. All of the paths 44-47 formed by consecutive state shifts that lead to the one same path of decode block 43, i.e. survivor path 48, are traced over the merge block 42. Paths 44-47 are merged for that in which they are the same and the least probable branches are disqualified in accordance with the selections of the ACSU 32, until there is only one path travelling through the merge section, which is formed by several of the consecutive individual branches depicted in FIG. 2. Following this, the path in question is decoded, resulting in the original bit sequence. The operation of the trace back memory 40 is therefore based on reaching the final decoded bit sequence as content of the decode block 43, by going over all stored paths one by one from the merge block""s new end to the old end (trace back) and merging the paths into one survivor path 48.
The tracing and merging of paths in the trace back memory is time-consuming, causing delays in the decoding process and therefore in reception and the entire data transfer. For the decoding process to be successful, the trace back memory has to be of a specific length. A common rule is that the length of the trace back memory""s merge block has been set to the encoder""s rate, i.e. the length of its shift register multiplied by 4 or 5. In the case of a convolution code formed with an encoder such as that depicted in FIG. 1, the shift register""s length, i.e. its rate, is 4, so the length of the merge block should be at least 16-20 states or cycles long. The length of this memory defines both the performance of the decoder in correcting errors and the minimum delay with which the decoded bit, at the earliest, can be received from the memory.
The lengths of the trace back memory""s blocks 41-43 can be altered without restriction and there can also be more than one read pointer. The more read pointers are used in memory space, the more paths can be merged at the same time. It is, however, difficult to make the method faster, even if the largest possible number of read pointers were used, because the merge block""s trace back operation takes at least as many cycles as the number of consecutive state columns, i.e. the length of the block in question, is. If, for example, the trace back is performed one bit at a time and the updating of each bit takes one cycle, updating a code of 110 bits lasts 110 cycles.
With the present invention, the time consumed in memory processing in connection with data transfer can be minimised or at least reduced, especially but not necessarily during the reception process and decoding. In the reception process, the memory needs to be updated continuously, because more data is continuously being received. This leads to the fact that the memory has to be regularly updated by deleting old data from the memory. The speed of this memory update operation can be increased with the invention.
The present invention is based on the idea that the memory update is done without going over the paths step by step such as in using the trace back method, but instead by copying first memory rows into second memory rows in accordance with the selections of the ASCU, adding the bit column with fixed values as the second memory""s first column and making the selection for the decoded bit based on the values of the second memory""s last column. Which first memory row is copied to which second memory row is based on information provided by the ACSU. Several paths are not merged into one; instead for that part in which the paths are the same, they are shown in the memory several times on different rows. This method of copying between memories leads to the fact that rows at the oldest end of the memory are normally the same, so the original bit can be detected from the memory""s last column. In a memory device corresponding to the invention, the paths formed by the state shifts are no longer seen as a bit sequence formed by consecutive states, but instead the last element of each row of the memory bank represents the original unencoded bit. Due to errors there may be differences in the oldest end of rows, so the final selection of the decoded bit can be made e.g. by a majority decision, by selecting the bit value that appears numerically the most in the last memory column.
The invention""s goal is achieved with parallel memory updating, which takes place by using two memories side by side by copying a bit row from the first memory (or memory section) to a bit row in the second memory (or memory section). The rows in the first memory are old (not updated) and the rows formed in the second memory are new (updated). The new fixed bit column is added as the second memory""s first column and the old rows of the first memory are copied after the second memory""s first column, based on the BMU""s information, so that the first memory""s first column is the second memory""s second column and the first memory""s second last column is the second memory""s last column. The second memory now contains the updated bit rows and the first memory""s last column is copied e.g. as a column after the last actual column of the second memory. The original decoded bit is found from the column in question by selecting the value that numerically appears the most in the column. In the next round, the second memory""s rows are old and the updated bit rows are copied to the first memory. The change of direction in the copying between memories is performed using simple logic and selection elements.
According to the first aspect of the invention, there is implemented a memory device for the storage of bit rows, characterised in that the memory device consists of a first memory matrix, which contains bit storage places in matrix form where the horizontally consecutive storage places form the first memory rows and the vertically consecutive storage places form the first memory columns; a second memory matrix, which contains bit storage places in matrix form where the horizontally consecutive storage places form the second memory rows and the vertically consecutive storage places form the second memory columns; an input for receiving selection data; addition means for adding fixed-value bits to the set first column as a default column for forming the bit values of the said second memory columns, in which each first column is a column among the said second memory columns; copying means for copying the contents of certain first memory rows row by row to the second memory rows while avoiding copying over the said default column, where the said received selection data affects the placement of the rows regarding which first memory row contents are copied to which second memory row, and for forming the bit values formed in the memory columns; and means for forming the initial bit value from the bit values of the defined second column, in which every second column is a column from the second memory columns.
According to a second aspect of the invention, there is implemented a method for memory management in the memory device, characterised in that the method consists of the following stages; selection data formed from the input bits is received; bits are copied from rows of the first memory matrix, which contains bit storage places in matrix form where the horizontally consecutive storage places form the first memory rows and the vertically consecutive storage places form the first memory columns, to rows of the second memory matrix, which contains bit storage places in matrix form where the horizontally consecutive storage places form the second memory rows and the vertically consecutive storage places form the second memory columns, in accordance with the said received selection data, fixed bit values are added to the second memory matrix to the defined first column for forming the default column from the said fixed bit values, in which each first column is a column among the said second memory columns; the contents of the said first memory rows are copied row by row to the said second memory rows while avoiding copying over the said default column in accordance with the said received selection data, while the said received selection data affects the rows"" placement regarding which first memory row content is copied to which second memory row; a column is added to the second memory matrix for storing fixed bit values as the said column; the set fixed bit values are stored as a column in the second memory matrix, upon which the said storage of the fixed bit values is performed to the said added column from the said second memory columns while the said column forms the default column; the initial bit value is formed from the second column bit values, in which every second column is a column among the second memory columns.
According to a third aspect of the invention, there is implemented a Viterbi decoder for use in decoding convolution codes, which consists of a branch metric unit for receiving the input bit and calculating the metric data, an Add-Compare-Select unit for forming selection data and a survivor memory unit for storing bit sequences, characterised in that the said survivor memory consists of a first memory matrix, which contains bit storage places in matrix form where the horizontally consecutive storage places form the first memory rows and the vertically consecutive storage places form the first memory columns, a second memory matrix, which contains bit storage places in matrix form where the horizontally consecutive storage places form the second memory rows and the vertically consecutive storage places form the second memory columns, an input for receiving selection data from the ACSU, additional equipment for adding fixed-value bits to the set first column as a default column for forming the bit values of the said second memory columns, in which each first column is a column among the said second memory columns, copying means for copying the contents of certain first memory rows row by row to the second memory rows while avoiding copying over the said default column, where the said received selection data affects the placement of the rows regarding which first memory row contents are copied to which second memory row and for forming the bit values formed in the memory columns; and means for forming the initial bit value from the bit values of the set second column, in which every second column is a column from the second memory columns.
According to a fourth aspect of the invention, there is implemented an electronic device, consisting of equipment for receiving a bit sequence, equipment for forming selection data from the said bit sequence, and survivor memory for storing the bits, characterised in that the said survivor memory consists of a first memory matrix, which contains bit storage places in matrix form where the horizontally consecutive storage places form the first memory rows and the vertically consecutive storage places form the first memory columns, a second memory matrix, which contains bit storage places in matrix form where the horizontally consecutive storage places form the second memory rows and the vertically consecutive storage places form the second memory columns, an input for receiving selection data from the ACSU, additional means for adding fixed-value bits to the set first column as a default column for forming the bit values of the said second memory columns, in which each first column is a column among the said second memory columns, copying means for copying the contents of certain first memory rows row by row to the second memory rows while avoiding copying over the said default column, where the said received selection data affects the placement of the rows regarding which first memory row contents are copied to which second memory row and for forming the bit values formed in the memory columns; and means for forming the initial bit value from the bit values of the set second column, in which every second column is a column from the second memory columns. An electronic device is a mobile communications device or a computer.